package com.wc.data_structures.hashtable;

/**
 * @Author congge
 * @Date 2023/4/24 23:00
 * @description 手写Hashtable
 */
class Hashtable<K, V> {
    private final Entry<?, ?>[] table;
    private int count;
    // 当count数量大于门限值得时候，数组需要扩容
    private int threshold;

    // 负载系数
    private final float loadFactor;

    public Hashtable() {
        this(11, 0.75f);
    }

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    /**
     * 初始化Hashtable
     *
     * @param initialCapacity 初始化数组容量
     * @param loadFactor      负载因子
     */
    public Hashtable(int initialCapacity, float loadFactor) {
        table = new Entry<?, ?>[initialCapacity];
        threshold = (int) Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE - 1);
        this.loadFactor = loadFactor;
    }

    /**
     * Hashtable中含多少个元素
     */
    public synchronized int size() {
        return count;
    }

    /**
     * Hashtable 是否为空
     */
    public synchronized boolean isEmpty() {
        return count == 0;
    }

    /**
     * 是否存在value值
     *
     * @param value 待查
     */
    public synchronized boolean contains(Object value) {
        if (value == null) {
            throw new NumberFormatException("value为空");
        }
        Entry<?, ?>[] tab = table;
        for (Entry<?, ?> entry : tab) {
            for (Entry<?, ?> e = entry; e != null; e = e.next) {
                if (e.value.equals(value)) {
                    return true;
                }
            }
        }
        return false;
    }

    public synchronized boolean containsValue(Object value) {
        return this.contains(value);
    }

    public synchronized boolean containsKey(Object key) {
        Entry<?, ?>[] tab = table;
        int hash = key.hashCode();
        int index = hash & 0x7FFFFFFF % tab.length;
        for (Entry<?, ?> e = tab[index]; e != null; e = e.next) {
            if (e.hash == hash && e.key.equals(key)) {
                return true;
            }
        }

        return false;
    }

    /**
     * 添加元素
     */
    public synchronized V put(K key, V value) {
        if (value == null) {
            throw new NullPointerException("value=null");
        }
        Entry<?, ?>[] tab = table;
        int hash = key.hashCode();
        /*
          这里hash & 0x7FFFFFFF是为了将这个数hash变为正数
          为什么不用Math.abs(hash) 呢，因为这个方法无法处理-2的32次方，但是正数只有2的32次方-1
         */
        int index = hash & 0x7FFFFFFF % tab.length;
        Entry<K, V> entry = (Entry<K, V>) tab[index];
        for (; entry != null; entry = entry.next) {
            if (entry.hash == hash && entry.key.equals(key)) {
                V oldValue = entry.value;
                entry.value = value;
                return oldValue;
            }
        }
        addEntry(hash, key, value, index);
        return null;
    }


    /**
     * @param hash
     * @param key
     * @param value
     * @param index
     */
    private synchronized void addEntry(int hash, K key, V value, int index) {
        Entry<?, ?>[] tab = table;
        if (count >= threshold) {
            rehash();
            tab = table;
            hash = key.hashCode();
            index = hash & 0x7FFFFFFF % tab.length;
        }
        Entry<K, V> e = (Entry<K, V>) table[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }

    public synchronized V remove(Object key) {
        Entry<?, ?>[] tab = table;
        int hash = key.hashCode();
        int index = hash & 0x7FFFFFFF % tab.length;
        Entry<K, V> e = (Entry<K, V>) tab[index];

        for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {
            if (e.hash == hash && e.key.equals(key)) {
                if (prev == null) {
                    tab[index] = e.next;
                    return e.value;
                } else {
                    prev.next = e.next;
                }
                count--;
                V oldValue = e.value;
                // 为了方便回收
                e.value = null;
                return oldValue;
            }
        }
        return null;
    }

    public synchronized V get(Object key) {
        Entry<?, ?>[] tab = table;
        int hash = key.hashCode();
        int index = hash & 0x7FFFFFFF % tab.length;
        Entry<?, ?> e = tab[index];

        for (; e != null; e = e.next) {
            if (e.hash == hash && e.key.equals(key)) {
                return (V) e.value;
            }
        }
        return null;
    }

    /**
     * 扩容
     */
    private synchronized void rehash() {
        Entry<?, ?>[] oldMap = table;
        int oldCapacity = oldMap.length;
        int newCapacity = oldCapacity << 1 + 1;

        /*
            防止内存达到最大值
         */
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE) {
                return;
            }
            newCapacity = Integer.MAX_VALUE - 1;
        }
        Entry<?, ?>[] newMap = new Entry<?, ?>[newCapacity];
        threshold = (int) Math.min(newCapacity * loadFactor, Integer.MAX_VALUE - 1);

        for (int i = 0; i < oldCapacity; i++) {
            for (Entry<K, V> old = (Entry<K, V>) oldMap[i]; old != null; ) {
                Entry<K, V> e = old;
                // 保证不断链
                old = old.next;
                int index = old.hash & 0x7FFFFFFF % newCapacity;
                // 头接法
                e.next = (Entry<K, V>) newMap[index];
                newMap[index] = e;
            }
        }
    }

    private static class Entry<K, V> {
        final K key;
        final int hash;
        V value;
        Entry<K, V> next;

        protected Entry(int hash, K key, V value, Entry<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        @Override
        public String toString() {
            return key + "=" + value;
        }
    }
}
